#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<assert.h>

void Swap(int* a,int* b)
{
  int temp = *a;
  *a = *b;
  *b = temp;
}
//冒泡排序
void BubbleSort(int* a,int n)
{
  for(int i = 0;i<n; i++)
  {
    int change=0;
    for(int j = 0;j<n-i-1;j++)
    {
      if(a[j]>a[j+1])
      {
        Swap(&a[j],&a[j+1]);
        change = 1;
      }
    }
    if(change==0) break;
  }
}
//堆排序
//1.堆向下调整
void AdjustDown(int* a,int n,int root)
{
  int parent = root;
  int child = parent*2+1;

  while(child<n)
  {
    if(child+1<n&&a[child+1]>a[child])
    {
      child += 1;
    }
    if(a[child]>a[parent])
    {
      Swap(&a[child],&a[parent]);
      parent=child;
      child = parent*2+1;
    }
    else 
    {
      break;
    }

  }
}
void HeapSort(int* a,int n)
{
  int i = 0;
  for(i=(n-1-1)/2;i>=0;i--)
  {
    AdjustDown(a,n,i);
  }
  int end = n-1;
  while(end)
  {
    Swap(&a[0],&a[end]);
    AdjustDown(a,end,0); 
    end--;
  }
}
//直接插入排序
void Insert(int* a,int n)
{
  int i=0;
  for(i=0;i<n-1;i++)
  {
    int end = i;
    int tmp= a[end+1];
    while(end>=0)
    {
      if(tmp<a[end])
      {
        a[end+1] = a[end];
        end--;
      }
      else 
      {
        break;
      }
    }
    a[end+1] = tmp;
  }
}
//选择排序
void SelectSort(int* a,int n)
{
  int i = 0;
  for(i=0;i<n;i++)
  {
    int start = i;
    int min = start;
    while(start<n)
    {
      if(a[start]<a[min])
      {
        min = start;
      }
      start++;
    }
    Swap(&a[i],&a[min]);
  }
}
//选择排序2

void SelectSort2(int* a,int n)
{
  int left = 0;
  int right = n-1;
  while(left<right)
  {
    int minindex = left;
    int maxindex = left;

    int i=0;
    for(i = left;i<=right;i++)
    {
      if(a[i]<a[minindex])
        minindex = i;
      if(a[i]>a[maxindex])
        maxindex = i;
    }
    Swap(&a[minindex],&a[left]);
    if(maxindex==left)
    {
      maxindex = minindex;//防止最大值位于序列开头，被最小值交换
    }
    Swap(&a[maxindex],&a[right]);
    left++;
    right--;

  }
}

//希尔排序
void ShellSort(int* a,int n)
{
  int gap = n;
  while(gap>1)
  {
    gap/=2;
    int i=0;
    for(i=0;i<n-gap;i++)
    {
      int end = i;
      int tmp = a[end+gap];
      while(end>=0)
      {
        if(tmp<a[end])
        {
          a[end+gap] = a[end];
          end-=gap;
        }
        else 
        {
          break;
        }
      }
      a[end+gap]=tmp;
    }

  }
}
//计数排序
void CountSort(int* a,int n)
{
  int min = a[0];
  int max = a[0];
  for(int i=0;i<n;i++)
  {
    if(a[i]<min) min=a[i];
    if(a[i]>max) max = a[i];
  }

  int range = max-min+1;
  int* count =(int*)calloc(range,sizeof(int));
  if(count==NULL)
  {
    printf("calloc fail");
    exit(-1);
  }
  for(int i=0;i<n;i++)
  {
    count[a[i]-min]++;
  }

  int i=0;
  for(int j=0;j<range;j++)
  {
    while(count[j]--)
    {
      a[i++] = j+min;
    }
  }

  free(count);
}
//快速排序，递归hoare版本
void QuickHoare(int* a,int begin,int end)
{
  if(begin>=end) return;
  int left = begin;
  int right = end;
  int keyi = left;

  while(left<right)
  {
    while(left<right&&a[right]>=a[keyi])
    {
      right--;
    }
    while(left<right&&a[left]<=a[keyi])
    {
      left++;
    }
    if(left<right)
    {
      Swap(&a[left],&a[right]);
    }    
  }

  int meeti=left;
  Swap(&a[keyi],&a[meeti]);

  QuickHoare(a,begin,meeti-1);
  QuickHoare(a,meeti+1,end);
}
//快排挖坑法
void Quicksort2(int* a,int begin,int end)
{
  if(begin>=end) return;
  int left = begin;
  int right = end;
  int key = a[begin];
  
  while(begin<end)
  {
    while(begin<end&&a[end]>=key)
    {
      end--;
    }
    a[begin] = a[end];
    while(begin<end&&a[begin]<=key)
    {
      begin++;
    }
    a[end]=a[begin];
  }

  int meeti = begin;
  a[meeti]= key;
  Quicksort2(a,left,meeti-1);
  Quicksort2(a,meeti+1,right);
}
//快排前后指针法
void Quicksort3(int* a,int begin,int end)
{
  if(begin>=end)return;
  int prev = begin;
  int cur = prev+1;
  int keyi = begin;
  while(cur<=end)
  {
    if(a[cur]<=a[keyi]&&++prev!=cur)//防止自己和自己交换
    {
      
      Swap(&a[prev],&a[cur]);
    }
      cur++;
  }
  Swap(&a[prev],&a[keyi]);
  Quicksort3(a,begin,prev-1);
  Quicksort3(a,prev+1,end);
}
//归并排序
void _MergeSort(int* a,int left,int right,int* tmp)
{
  if(left>=right)  return;
  int mid = left+(right-left)/2;
  _MergeSort(a,left,mid,tmp);
  _MergeSort(a,mid+1,right,tmp);

  int begin1 = left, end1 = mid;
  int begin2 = mid+1, end2 = right;

  int i = left;
  while(begin1<=end1&&begin2<=end2)
  {
    if(a[begin1]<a[begin2])
    {
      tmp[i++] = a[begin1++];
    }
    else 
    {
      tmp[i++] = a[begin2++];
    }
  }

  while(begin1<=end1)
    tmp[i++] = a[begin1++];
  while(begin2<=end2)
    tmp[i++] = a[begin2++];
  int j=0;
  for(j=left;j<=right;j++)
  {
    a[j] = tmp[j];
  }

}

void print(int* a,int n)
{
  for(int i=0;i<n;i++)
  {
    printf("%d  ",a[i]);
  }
  printf("\n");
}

int main()
{
  int a[10] = {5,4,3,2,1,6,7,8,9,10};
  int* tmp = (int*)malloc(sizeof(int)*10);
  // BubbleSort(a,10);
  //HeapSort(a,10);
  // Insert(a,10);
  //SelectSort2(a,10);
  //ShellSort(a,10);
  // CountSort(a,10);
  //Quicksort3(a,0,9);
  _MergeSort(a,0,9,tmp);
  print(a,10);
  return 0;
}
